# 二叉树的最大深度

# 凡是遇到二叉树的，一般递归都可以解决问题
# 判断根节点是否为空，为空就返回0.不为空就是他的左右子树的深度的最大值 + 1
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        # 二叉树的最大深度
        if root == None:
            return 0
        return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1

import collections
# 有递归就有迭代法。迭代法的主要思路就是每次处理队列中只剩下一个行。那你就每次处理一个行看看最终有多少个行就行了
def maxDepth(self, root: TreeNode) -> int:
    if not root:    return 0
    deque = collections.deque([root])   # 加入跟，是一层
    ans = 0
    while deque:
        size = len(deque)   # 树的这一行有多少个数
        while size > 0:
            node = deque.popleft() # 拿出该行的一个，下面要添加他的左右子树进去
            if node.left:
                deque.append(node.left)
            if node.right:
                deque.append(node.right)
            size = size - 1
        ans = ans + 1
    return ans

